In computer graphics, it is often important to extract objects shown in the foreground of an image from the background of that image. The extraction of these objects is known as alpha matting. Alpha matting takes as its input a trimap image representing foreground, background, and unknown regions. Pixels of the unknown regions may be partially transparent, blending the foreground and the background, or may belong entirely to one of the foreground or background. The output of alpha matting is the alpha matte of each pixel, the alpha matte being a measure of the opacity of the pixel with respect to the foreground. These alpha mattes are stored in the alpha channel for each pixel and have values between 0 and 1. Background pixels may be assigned a value of 0, foreground pixels a value of 1, and unknown pixels may have values of 0, 1, or values in between depending on their degree of opacity with respect to the foreground.
Existing alpha matting techniques include propagation-based alpha matting and sample-based alpha matting. Propagation-based techniques treat the problem as interpolating the unknown alpha matte values from the known regions. The interpolation can be done by solving an affinity matrix, by optimizing Markov Random Fields, or by computing geodesic distances. These techniques mainly rely on the image's continuity to estimate the alpha matte, and do not explicitly account for the foreground and background colors. They have shown success in many cases, but may fail when the foreground has long and thin structures or holes. Their performance can be improved when combined with sampling-based techniques.
Sample-based techniques first estimate the foreground and background colors and then compute the alpha mattes. Some sample-based techniques attempt to fit a parametric model to the color distributions, but these techniques are less valid when the image does not satisfy the model. Other sample-based techniques are non-parametric: they pick out some color samples from the known regions to estimate the unknown alpha matte values. These techniques perform well when the pixels in the sample set include foreground and background colors. However, the foreground and background colors are not always covered, because these sample-based techniques only collect samples near each unknown pixel, limiting the number of sample pixels and their colors.